class Solution {
public:
    bool isInterleave(string s1, string s2, string s3)
    {
        if(s1.length() + s2.length() != s3.length())
            return false;
        if(s1.length() < s2.length())
            return isInterleave(s2, s1, s3);

        vector<bool> f(s2.length() + 1, true);
        for(size_t i = 1; i <= s2.length(); ++i)
            f[i] = (s2[i - 1] == s3[i - 1]) && f[i - 1];

        for(size_t i = 1; i <= s1.length(); ++i) {
            f[0] = (s1[i - 1] == s3[i - 1]) && f[0];

            for(size_t j = 1; j <= s2.length(); ++j)
                f[j] = (s1[i - 1] == s3[i + j - 1] && f[j])
                       || (s2[j - 1] == s3[i + j - 1] && f[j - 1]);
        }
        return f[s2.length()];
    }
};
